package com.xmg.sort;

import java.util.Arrays;
import java.util.Collections;

public class SortDemo {
    public static void main(String[] args) {
        int[] arr = {6,4,23,5,7,8,9,2,1,3};

//        int[] arr = new int[80000];
//        for (int i = 0; i < 80000; i++) {
//            arr[i] = (int) (Math.random()*8000000);
//        }
        long start = System.currentTimeMillis();
//        selectSort(arr);

//        bubbleSort(arr);

//        straightInsertionSort2(arr);

//        binaryInsertSort(arr);

//        shellSort2(arr);
//        quickSort(arr,0,arr.length-1);
        int temp[] = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
        System.out.println(System.currentTimeMillis()-start);
    }

    /**
     * 选择排序
     * 每次选择一个元素和后面的所有元素进行对比，并按照排序规则进行比对并交换，每轮选中一个极值放到最前(后)端
     * @param arr
     */
    private static void selectSort(int[] arr){
        int min,temp;
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            min = i;
            for (int j = i+1; j < len; j++) {
                if(arr[j]<arr[min]){
                    min = j;
                }
            }
            if(min!=i){
                temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }

    /**
     * 冒泡排序
     * 相邻数据两两比较，每次将最大或最小的元素放到最后
     * @param arr
     */
    private static void bubbleSort(int[] arr){
        int len = arr.length;
        int temp;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < len - i; j++) {
                if(arr[j]>arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

    /**
     * 直接插入排序
     * 默认前面n个元素已经排好序，第n+1个元素依次和这n个元素进行比较，找到合适的位置插入
     * @param arr
     */
    private static void straightInsertionSort(int[] arr){
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            int key = arr[i];
            int j = i-1;
            while (j>=0 && arr[j]>key){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = key;
        }
    }

    private static void straightInsertionSort2(int[] arr){
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            int key = arr[i];
            int j = i-1;
            for(;j>=0&&arr[j]>key;j--){
                arr[j+1] = arr[j];
            }
            arr[j+1] = key;
        }
    }

    /**
     * 二分插入排序
     *在直接插入的基础上进行了改动，插入第i个元素时，对前面i-1个元素进行折半，跟中间的元素进行比较，根据比较结果再选择左边或者右边折半
     * @param arr
     */
    private static void binaryInsertSort(int[] arr){
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            int key = arr[i];
            int low = 0,high = i-1;
            int mid = -1;
            while (low <= high){
                mid = low + (high - low)/2;
                if(arr[mid]>key){
                    high = mid -1;
                }else{
                    low = mid +1;
                }
            }

            for(int j = i-1;j>=low;j--){
                arr[j+1] = arr[j];
            }
            arr[low] = key;
        }
    }

    /**
     * 希尔排序（交换式  效率低）
     * @param arr
     */
    private static void shellSort(int[] arr){
        int temp = 0;
        for (int gap = arr.length/2;gap>0;gap /= 2){
            for (int i = gap;i<arr.length;i++){
                for (int j = i-gap; j >=0 ; j -=gap) {
                    if (arr[j] > arr[j+gap]) {
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
        }
    }
    //对交换式希尔排序进行优化  移位法  按照固定间隔进行的插入排序
    public static void shellSort2(int[] arr){
        for (int gap = arr.length/2;gap>0;gap /= 2){
            for (int i = gap; i <arr.length ; i++) {
                int j = i;
                int temp = arr[j];
                while (j-gap>=0&&arr[j-gap]>temp){
                    arr[j] = arr[j-gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }

    /**
     * 快速排序法
     * @param arr
     */
    public static void quickSort(int[] arr,int head,int tail){
        if (head >= tail || arr == null || arr.length <= 1) {
            return;
        }
        int i = head, j = tail, pivot = arr[(head + tail) / 2];
        while (i <= j) {
            while (arr[i] < pivot) {
                ++i;
            }
            while (arr[j] > pivot) {
                --j;
            }
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                ++i;
                --j;
            } else if (i == j) {
                ++i;
            }
        }
        quickSort(arr, head, j);
        quickSort(arr, i, tail);
    }

    public static void mergeSort(int[] arr,int left,int right,int[] temp){
        if (left<right) {
            int mid = (left + right) / 2;

            mergeSort(arr,left,mid,temp);

            mergeSort(arr,mid+1,right,temp);

            merge(arr,left,mid,right,temp);
        }
    }

    /**
     * 归并排序 合方法
     * @param arr   原始数组
     * @param left  左边有序序列的初始索引
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  做中转的数组
     */
    public static void merge(int[] arr,int left,int mid, int right, int[] temp){
        int i = left;//左边有序序列的初始索引
        int j = mid + 1;//右边有序序列的初始索引
        int t = 0;  //指向temp数组的当前索引
        //先把左右两边(有序)的数据按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完为止
        while(i<=mid&&j<=right){
            if(arr[i]<=arr[j]){
                temp[t] = arr[i];
                t += 1;
                i += 1;
            }else{
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }

        //把有剩余数据的一边的数据依次全部填充到temp
        while (i<=mid){
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }

        while (j<=right){
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }

        //将temp数组拷贝到arr，注意：并不是每次都拷贝所有
        t = 0;
        int templeft = left;
        while (templeft <= right){
            arr[templeft] = temp[t];
            t += 1;
            templeft +=1;
        }
    }
}